/*
 * Copyright 北京航空航天大学 @ 2015 版权所有
 */
package com.buaa.edu.leetcode.algorithm.hash;

import java.util.HashMap;
import java.util.Map;

/**
 * <p>
 * 最小窗口字符串 
 * 给定字符串 S和T, 查找S中最小字符串，该字符串包含T且线性时间复杂度完成，如果多个返回第一个
 * 例1：S = "ADOBECODEBANC" T = "ABC" 最小窗口为  "BANC".
 * 例2：S = "AFEGCABC" T = "FACE" 最小窗口为  "FEGCA" 或者 "AFEGC",返回第一个为AFEGC
 * </p>
 * 
 * @author towan
 * @email tongwenzide@163.com 
 * @time 2015年5月25日
 */
public class MinimumWindowSubstring {

  public String minWindow(String s, String t) {
        if(t==null || t.length() == 0){
            return "";
        }
        int sLen = s.length();
        int tLen = t.length();
        
        //记录目标字符串中每个不同字符的个数
        Map<Character,Integer> tMap = new HashMap<>();
        for(int i=0;i<tLen;i++){
            char ch = t.charAt(i);
            if(tMap.containsKey(ch)){
                tMap.put(ch, tMap.get(ch)+1);
            }else{
                tMap.put(ch, 1);
            }
        }
        
        //记录原串中字符的个数
        Map<Character,Integer> sMap = new HashMap<>();
        int count = 0;
        int start = 0;
        int minLen = Integer.MAX_VALUE;
        int minLenStart = -1;
        
        for(int i=0;i<sLen;i++){
            char ch = s.charAt(i);
            //忽略不再目标串的字符
            if(!tMap.containsKey(ch)){
                continue;
            }
            if(sMap.containsKey(ch)){
                sMap.put(ch, sMap.get(ch)+1);
            }else{
                sMap.put(ch, 1);
            }
            
            if(sMap.get(ch) <=tMap.get(ch)){
                count++;//统计已有字符的个数
            }
            if(count>=tLen){
                char c = s.charAt(start);
                while(sMap.containsKey(c)==false || sMap.get(c)>tMap.get(c)){
                    if(tMap.containsKey(c)){
                        sMap.put(c, sMap.get(c)-1);
                        //满足这个条件，尽量向右移动
                    }
                    start++;
                    c = s.charAt(start);
                }
                int len = i-start+1;
                if(len<minLen){//保存最小窗口
                    minLen = len;
                    minLenStart = start;
                }
            }
        }
        String result = "";
        if(minLenStart >=0){
          result = s.substring(minLenStart, minLenStart+minLen);
        }
        return result;
    }

    public static void main(String[] args) {
        String s = "ADOBECODEBANC";
        String t = "ABC";
        MinimumWindowSubstring windowSubstring = new MinimumWindowSubstring();
        System.out.println(windowSubstring.minWindow(s, t));
    }
}
